//Given an array of positive integers nums and a positive integer target, 
//return the minimal length of a contiguous subarray [numsl, numsl+1, ..., numsr-1, 
//numsr] of which the sum is greater than or equal to target. If there is no such 
//subarray, return 0 instead. 
//
// 
// Example 1: 
//
// 
//Input: target = 7, nums = [2,3,1,2,4,3]
//Output: 2
//Explanation: The subarray [4,3] has the minimal length under the problem 
//constraint.
// 
//
// Example 2: 
//
// 
//Input: target = 4, nums = [1,4,4]
//Output: 1
// 
//
// Example 3: 
//
// 
//Input: target = 11, nums = [1,1,1,1,1,1,1,1]
//Output: 0
// 
//
// 
// Constraints: 
//
// 
// 1 <= target <= 10⁹ 
// 1 <= nums.length <= 10⁵ 
// 1 <= nums[i] <= 10⁵ 
// 
//
// 
//Follow up: If you have figured out the O(n) solution, try coding another 
//solution of which the time complexity is O(n log(n)). Related Topics Array Binary 
//Search Sliding Window Prefix Sum 👍 5305 👎 166


package leetcode.editor.en;

public class _209_MinimumSizeSubarraySum {
    public static void main(String[] args) {
        Solution solution = new _209_MinimumSizeSubarraySum().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int minSubArrayLen1(int target, int[] nums) {
            int l = 0,r = 0;
            int sum = 0, min = Integer.MAX_VALUE;
            while (r<nums.length){
                sum+= nums[r];
                while (l<=r &&sum>=target){
                    min = Math.min(r-l+1, min);
                    sum-=nums[l++];
                }
                r++;
            }
            return min==Integer.MAX_VALUE?0:min;
        }

        public int minSubArrayLen(int target, int[] nums) {
            int i = 0, result = Integer.MAX_VALUE, sum = 0;
            for (int j = 0; j < nums.length; j++) {
                sum+=nums[j];
                while (sum >= target) {
                    result = Math.min(result, j-i+1);
                    sum-=nums[i++];
                }
            }
            return result == Integer.MAX_VALUE?0:result;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}